package algorithm.dynamicProgramming.leetcode;

//918. 环形子数组的最大和

/**
 * 分为两种情况，第一种是用不到环形数组，所以直接求数组中的最大子序列就行
 *            第二种是用到环形数组，要是用到那么一定会用到第一个元素和最后一个元素，
 *            说明第二个---倒数第二个中间有负数，否则用不到环形
 *            求出这中间的最小子序列，然后用整个数组的和 减去最小子序列 就是最大值
 */
public class MaxSubarraySumCircular {
    public static void main(String[] args) {

    }

    //动态规划
    public int maxSubarraySumCircular(int[] nums) {

        int[] f = new int[nums.length];
        f[0] = nums[0];
        int min = 0;
        for (int i=1;i<nums.length-1;i++){
            f[i] = Math.min(f[i-1]+nums[i],nums[i]);
            min = Math.min(min,f[i]);
        }

        int max = nums[0];
        int sum = nums[0];
        for (int i=1;i<nums.length;i++){
            f[i] = Math.max(f[i-1]+nums[i],nums[i]);
            max = Math.max(f[i],max);
            sum+=nums[i];
        }
        return Math.max(sum-min,max);
    }
}
